For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
25 views

generating function as english statement

An ordinary enumerator is given as $(1+x+x^2)^p$. This is being understood as follows: There are 2 each of p kinds of objects.The ordinary enumerator for selecting none (or) one (or) both the ...
0
votes
0answers
17 views

Finding a closed formula for a summation containing elementary symmetric function

Let $i$ and $n$ be non negative integers and let $X=(x_1,x_2,...,x_n)$ be a finite sequence of variables. The expression $S_i(X)$ is then defined as follows: If $i>n$, then $S_i(X):=0$, Otherwise ...
1
vote
1answer
28 views

A little problem with a binomial identity

I have to compute the quantity $\sum\limits_{k=0}^{n-1} \binom{n}{k} \frac{k}{n-k}$. Using the identity $k\binom{n}{k}=n\binom{n-1}{k-1}$ and reindexing the sum, it's easy to see the previous sum ...
0
votes
2answers
55 views

Two new binomial identities [closed]

I have to compute the following values: $$ 1) \sum\limits_{k=0}^{n-1} 2^k \binom{n-1}{k} \frac{k}{n-k} $$ $$ 2) \sum\limits_{k=0}^{n-1} 2^{n-k} \binom{n-1}{k} \frac{k}{n-k} $$ How can I solve them? ...
3
votes
3answers
57 views

Fountains of Coins and Fibonacci Numbers

I recently came across a problem in Herbert Wilf's Generatingfunctionology book that I can't come up with an elegant solution to and can't find any solutions online. The problem statement begins on ...
0
votes
1answer
22 views

Proving that a binomial coefficient involving a power of $2$ is even

In the process of proving that the polynomial $x^{2^n} + 1$ is irreducible in $\mathbb{Z}[x]$, I am getting stuck on proving an intermediate result: Denote $f(X)=X^{2^n}+1.$ By a linear change of ...
1
vote
0answers
16 views

First to note the relation between Stasheff polytopes (associahedra) and compositional inversion?

In my answer to MO-Q: Enumerative geometry and nonlinear waves, I outline the relation between the refined face polynomials of the Stasheff polytopes (associahedra) and the partition polynomials for ...
2
votes
2answers
62 views

Pearl necklace combinations

A string contains 36 different pearls: 12 blue, 12 green and 12 red. When the strings ends are unconnected the number of possible combinations to arrange the pearls is $36 \choose 12 $ $\times $ $24 ...
1
vote
1answer
27 views

maximum intersections between circles and lines

How do I go about systematically finding the maximum number of intersections between n lines and k circles? I don't wish to draw it out. For example if there are 2 circles and 3 lines then the maximum ...
4
votes
0answers
113 views

Is there a closed-form expression for Shapley value of glove game?

Suppose we have a coalition game with transferable utilities, with $m$ players having a right-handed glove and $n$ players having a left-handed glove. The value of a coalition is equal to the number ...
8
votes
1answer
140 views

Meeting of people.

In a group of k people, some are acquainted with each other and some are not. There are two rooms for dinner. Every person chooses to stay in that room, in which he has an even number of ...
1
vote
1answer
58 views

Problem with the application of the pigeonhole principle.

A football team plays at least one match per day in a month of $30$ days , but no more than $45$ matches in that month. Is it true that in some consecutive days in the month, the team will play ...
2
votes
1answer
31 views

How many triangles can be made from $n$ points on a line and not on a line

We have a plane with $n$ points $(n\ge 34)$. $17$ points are on one line, and the rest are positioned such that no three points are on one line. How many triangles can we make from the $n$ points? ...
2
votes
1answer
51 views

Dominoes on chessboard

A $2016\times 2016$ chessboard is tiled with $2 \times 1$ dominoes. I can prove that there is a grid line that pass through at least $505$ dominoes. But how to prove or disprove that there is a ...
2
votes
3answers
103 views

How often does a one-dimensional lazy random walk end at the origin?

This seems like it's probably a solved problem, but I don't seem to be googling the right keywords. I want to know the probability that a lazy random walk on $\mathbb{Z}$ ends where it started. To be ...
2
votes
1answer
29 views

Find the number of times K appears in any 4 item subset of T

Given the set T of all K {1, 2, 3, 4, 5, 6, 7, 8, 9} Let N be 4. There can be produced 126 combinations of N items, as subsets S. Every K has an equal ...
2
votes
0answers
97 views

Balls and bins counting problem with some indistinguishable balls and cap on number of indistinguishable balls per bucket

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are ...
0
votes
2answers
40 views

Represent a four letter word as a number

I am trying to do some things in mysql and c++, and I wonder, is there a way to convert a word to a number such that I can recover the word from the value of the number? Each word represents an ID ...
0
votes
2answers
59 views

Finding a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in

Find a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in. $a_n=\begin {cases}A\text{____}a_{n-1}\\ B\text{____}a_{n-1}\\ C\text{____}a_{n-1}\\ ...
1
vote
0answers
40 views

counting unique paths in 2D

For a one-diemnsional sequence $\mathbf{a}=[a_1 a_2 \space … \space a_N]$, there are exactly two ways in which I can read/scan (without repetition) this sequence i-e $s_1=[a_1 \space a_2 \space … ...
1
vote
1answer
30 views

How many subsets of $\{1,2…,n\}$ there are such that if $2$ exists in the set then $1$ isn't

How many subsets of $\{1,2...,n\}$ there are such that if $2$ exists in the set then $1$ isn't? I think the approach is a recursive formula: Let $b_n$ be the sequence: If $2$ is in the set then ...
0
votes
1answer
41 views

finding total number of subset pairs of a set that has equal xor??

I recently came across a problem where i need to find the total number of subset pairs which has equal xor value for a given set. Like for following example: ...
0
votes
3answers
34 views

We are given a class consisting of 4 boys and 4 girls.

We are given a class consisting of 4 boys and 4 girls. a committee that consists of a President, a Vice-President and a secretary is to be chosen among the 8 students of the class. Let a denote the ...
16
votes
3answers
1k views

Why do graph degree sequences always have at least one number repeated? [duplicate]

Why do graph degree sequences always have at least one number repeated? $(1, 2, 2, 3)$ = Valid, as you can see, because the $2$ is repeated. $(1, 2, 3)$ = Not possible to construct a graph with ...
3
votes
1answer
89 views

A Generalized version of Inclusion-Exclusion Principle?

I recently read Doron Zeilberger's paper on Inclusion-Exclusion Principle. Let's say there are $n$ properties which are numbered $1,\cdots,n$. And let $A$ be a set of elements which has some of ...
1
vote
1answer
40 views

Combination problem: retrieve four kinds of objects with restriction [duplicate]

How many ways are there to select (combinations) $n$ objects from $a$ identical objects of first kind, $b$ identical objects of second kind, $c$ identical objects of third kind and $d$ identical ...
1
vote
1answer
34 views

Symmetric Polynomials and Automorphisms of Complex Polynomial Rings

I asked a version of this question earlier, but it was very imprecise and poorly formatted, so I decided to create a new question. Suppose we have an ordered set of $n(n-1)/2$ distinct polynomials ...
7
votes
1answer
97 views

What would be the mathematical solution to this question?

I know that usually, your not supposed to ask homework questions, but I figure it's ok now, as I've already kind of solved it. Three clever monkeys divide a pile of bananas. The first monkey takes ...
0
votes
1answer
41 views

product free, property P

In jurnal mocow jurnal combinatorik and number theory "multiplicative property of set residue say in paragraph one, say for every positive integer, every set of residues mod of cardinality larger than ...
0
votes
1answer
34 views

Simple Combinations Word problem.

A boy is preparing for test. The teacher gives $30$ questions to study from and will select $10$ out of the $30$. The student only know hows to solve $25$ of the $30$ questions. What is the ...
1
vote
1answer
57 views

Product of $n(n-1)/2$ polynomials of the same degree is symmetric

I am trying to prove a simple fact about polynomials in the multivariate polynomial ring $\mathbb{C}[x_1,x_2,...x_n]$, for $n \gt 3$ but I've been getting stuck. EDIT: After a comment by Tad I ...
1
vote
1answer
39 views

BMO1 2005/06 Question 4 Combinatorics Problem

The equilateral triangle $ABC$ has sides of integer length $N$. The triangle is completely divided (by drawing lines parallel to the sides of the triangle) into equilateral triangular cells of side ...
3
votes
3answers
26 views

I have 30 photos, which I want to sort into 2 categories. Either one can be empty. How many ways can I sort these photos, order matters?

I know the answer is $\binom{31}{1}\cdot30!$, and I understand the reasoning as organizing $30!$ ways and then $\binom{31}{1}$ places to put the delimiter. Why is it not $2^{30}\cdot30!$ That is, ...
2
votes
1answer
20 views

Find the number of ascending integers which are less than $10^9$

A positive integer $d$ is said to be ascending if in its decimal representation $d = d_md_{m-1}\ldots d_2d_1$ we have $0<d_m\leq d_{m-1}\le\cdots\leq d_2\leq d_1$. For example $112233$ or ...
3
votes
3answers
101 views

Find the number of integer solutons to $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60$.

Find the number of integer solutons to $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60$ if $x_1 \geq2, x_2\geq 5, 2\leq x_3\leq 7, x_4\geq 1, x_5\geq 3, x_6\geq 2$. Here is my approach: If you let $M = ...
0
votes
1answer
24 views

Statistical/Combinatorial: How to analyze?

I'm currently preparing for my exam and in the process trying to solve some statistical problems. The question goes as follows: Q1: A book consisting of 269 pages contains 40 missprints. Only, you ...
-1
votes
0answers
41 views

Finding minimum base set of a group of numbers

I'm trying to solve this problem. I'd appreciate an algorithm and (hopefully) a recommendation on programming languages that makes writing a solver easy. (correct & easy >> fast, but I'm working ...
1
vote
2answers
28 views

Married couples around a table(2)

This is in connection with my previous question. Suppose the question is "How many ways can three married couples sit around a round table if husband and wife must sit opposite each other" My ...
1
vote
0answers
19 views

Rusza triangle inequality and approximate groups.

Feel free to scroll down to the "Question" section if you're familiar with the notation of Tao and Vu's Additive Combinatorics, which I believe is standard notation for the field. Notation Let $Z$ ...
0
votes
1answer
48 views

I want to find the closed form of $\sum\limits _{i=0}^{\lfloor n/2 \rfloor} {n-i \choose i}$ [duplicate]

I can't find the starting points. Thank you for your help.
3
votes
1answer
44 views

There are 39 students in our class. We form groups of 2, with one left out. How many ways can the students be paired up?

I know that the answer is $\frac{39!}{(2!)^{19}\cdot19!}$, where each pair can be organized $2!$ ways and the pairs can be arranged in $19!$ ways. We can also extrapolate the case for $5$ students, ...
1
vote
1answer
38 views

Married couples around a table

There are lot of similar questions available. After going through all, I am still confused with two different answers. Question : How many ways can three married couples sit around a round table if ...
3
votes
1answer
25 views

How many ways can 8 persons, including Peter and Paul, sit in a row with Peter and Paul not sitting next to each other?

The solution I have to this problem is $8!-2\cdot7!$. I don't understand why the $7!$ is multiplied by two. My solution is that you have a total $8!$ ways to organize 8 people. Subtract all cases ...
1
vote
2answers
38 views

Derive formula for number of cables in full-mesh network

I am trying to determine how they derived number of cables needed in a full mesh network According to networking books it is $\dfrac{N * (N-1)}{2}$, where N is the number of nodes. I tried drawing ...
1
vote
1answer
51 views

How many bags can be made out of 4 kinds of balls

We have balls in a bin, $30$ balls of type $a$, $30$ balls of type $b$, $30$ balls of type $c$, $30$ balls of type $d$. We take out one ball per minute in random and move it to a bag. How ...
7
votes
1answer
139 views

Partition Generating Function

a) Let $$P(x)=\sum_{n=0}^{\infty} p_nx^n=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+\cdots$$ be the partition generating function, and let $Q(x)=\sum_{n=0}^{\infty} q_nx^n$, where $q_n$ is the number of ...
5
votes
0answers
220 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
2
votes
2answers
51 views

Combinatorics of given alphabet

I'm looking for the formula to determine the number of possible words that can be formed with a fixed set of letters and some repeated letters. For instance take the 8-letter word SEASIDES and find ...
3
votes
0answers
46 views

Find naturals that are sum of numbers with the same digits in inverse order

In a test I've found the following exercise: We say $n \in \mathbb{N}$ is reflexive if is the sum of two naturals $x$ and $y$ such that $y$ has the same digits of $x$ witten in the inverse order ...
1
vote
3answers
61 views

Two combinatorial identities

I have to compute the following quantity: $$ 1) \sum\limits_{k=0}^{n} \binom{n}{k}k2^{n-k} $$ Moreover, I have to give an upper bound for the following quantity: $$ 2) \sum\limits_{k=1}^{n-2} ...