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)

0
votes
0answers
19 views

Reducing the form of $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$.

I've been toying around with simplifying the expression $2\sum\limits_{j=0}^{n-2}\sum\limits_{k=1}^n {{k+j}\choose{k}}{{2n-j-k-1}\choose{n-k+1}}$ (for integer only $n$) for a while, as I was hoping it ...
1
vote
2answers
16 views

Probability of choosing two bulbs with the same rating given that one has a specific rating

I am trying to teach myself statistics, and working through Jay DeVore's excellent text of "Probability and Statistics for Engineering and the Sciences". The problem is as follows: We have box of the ...
4
votes
1answer
27 views

Counting problem - verification please?

A question we did in class asks: "In how many ways can we put 4 girls and 4 boys on a row (so order matters) so that a certain girl and a certain boy are always seated next to each other, and no 2 ...
-1
votes
0answers
22 views

In how many ways can five different keys be put in a flat leather key case? [on hold]

In how many ways can five different keys be put in a flat leather key case?
-4
votes
1answer
31 views

In how many ways can two chocolate chip, three raisin, and one peanut butter cookie be distributed to six children? [on hold]

A mother has six cookies, two chocolate chip, three raisin, and one peanut butter. In how many distinct ways can she pass them out to six children so that each gets one? Assume that those of the ...
0
votes
0answers
13 views

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
1
vote
0answers
25 views

Pattern Inventory - even and odd [on hold]

Say we have the following Pattern Inventory: \begin{align*} \text{Inve}(a, b, c,d) = \end{align*} \begin{align*} \frac{1}{16}\bigg(\big(a + b + c + d\big)^{8} + \big(a^2 + b^2 + c^2 + d^2\big)^4 + ...
-2
votes
1answer
16 views

Questions regarding seating arrangements [on hold]

Consider there are $9$ people and $3$ tables that sits the following way ($5$ chairs, $3$ chairs and $2$ chairs). How many combinations if order matters to the people being seated and no chair can be ...
3
votes
1answer
40 views

Why this solution of the birthday problem is wrong? [duplicate]

If we have $n$ people there are $n(n-1)/2$ possible pairs that we can find. The probability that any two people have the same birthday is $1/365$. So for $n$ people the probability of finding at least ...
4
votes
3answers
54 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
0answers
30 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
0
votes
0answers
37 views

When will the game end? [on hold]

Two men are playing a game. They have a card deck consisting of exactly 10 cards, numbered from 1 to 10, and all values are different. On each turn a fight happens. Each of them picks one card from ...
1
vote
0answers
16 views

Lines and planes-recursive formula

A family of $n$ lines is drawn in the plane such that each pair of lines cross and no $3$ dinstinct lines have a point in common Let $r(n)$ denote the number of regions into ...
1
vote
4answers
39 views

How many ways can you choose $4$ teams of $2$ from $8$ people.

How many ways can you choose $4$ teams of $2$ from $8$ people. My thoughts were that you have $8$ slots to be filled so you have $8!$ ways to arrange them but this overcounts by a factor of $2$ since ...
0
votes
1answer
60 views

Tricky question about binomial expansions. [duplicate]

State the binomial expansion of $(1+x)^n$ So I can do this $$(1+x)^n=\sum_{i=0}^{n} {n\choose i}x^i$$ Then given $n=2k$ is even. Derive an expression for $$\sum_{i=0}^{2k} (-1)^i{2k\choose i}$$ ...
2
votes
1answer
68 views

Trirectangular tetrahedron

Looking at http://mathworld.wolfram.com/TrirectangularTetrahedron.html I wonder what the symmetry group of a trirectangular tetrahedron is?
1
vote
4answers
70 views

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000$.

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000.$ My attempt: False, Let set $z = \{1,2,3\}$ then $|z|^{|x|}$ is set of function $y:x\to z.$ $|x| = n$ and $|z| = ...
-4
votes
1answer
25 views

Four letters {A, B, C, D} are arranged in a line. What is the probability that A and B will be next to each other? [on hold]

Four letters $\{A, B, C, D\}$ are arranged, with no repetitions and always using the four. What is the probability that $A$ and $B$ will be next to each other?
1
vote
0answers
18 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
1
vote
2answers
57 views

Probability in a Restaurant

In a revolving restaurant, there are four round tables each with three seats. How many different ways can $12$ people sit in this restaurant? This is what I think the answer is: $$\binom{12}{4} ...
0
votes
1answer
39 views

How to find weight function using generating series?

How to find the weight function and corresponding set given the generating series? Is there a general method for this kind of problems, I am preparing for an olympiad. Consider the below example: ...
1
vote
1answer
40 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
40 views

Lights out - foobar - optimise python implementation beyond binary matrix solver

I'm looking for further details on solving 'Lights out' puzzle, as asked in foobar challenge. Sorry I don't have enough credit to add/comment on existing threads, but I'm interested in a specific ...
3
votes
4answers
41 views

6 people are holding a show, one at a time, such that person $x$ has to go after person $y$ and person $z$. How many ways could the show be held?

Let's say the people are called $a$, $b$, $c$, $x$, $y$, $z$ My initial thinking was to go by fixing "$x$" in a certain position, so: $\underline {} \underline {} \underline {}\underline ...
1
vote
1answer
15 views

How do I get number of combination for pairs of football teams?

Suppose we have 8 football teams playing each other in 4 matches. How do I find the number of combinations that is possible? E.g. Teams A,B,C,D,E,F,G,H can be in the following matches: Match 1: A vs ...
0
votes
1answer
56 views

combinatorics contest problem

Question: Calvin has a bag containing $50$ red balls, $50$ blue balls, and $30$ yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out $5$ more red ...
1
vote
4answers
48 views

Combinatorics: Simplify the generating function $x^0+x^2+x^4+\cdots$

This is probably going to have a simple solution, and I'm going to kick myself when I see it, but I have a bit of mental block on this topic in general that I'm trying to clear before the next year of ...
2
votes
1answer
37 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
2
votes
2answers
34 views

How many possible orders are there?

A tapas bar serves 15 dishes, of which 7 are vegetarian, 4 are fish and 4 are meat. A table of customers decides to order 8 dishes, possibly including repetitions. a) Calculate the number of possible ...
0
votes
0answers
17 views

What's the approximation of such a combination? [duplicate]

Given $k,m, k \leq m$. $N=\binom {m+k}{m}$ What's the approximation of N?
7
votes
0answers
54 views

In how many ways can the integers from $1$ to $n$ be divided into two groups with the same sum?

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum? I have tried calculating some of these values for small $n$, but cannot seem to find a pattern. Any ...
2
votes
0answers
23 views

Combinatorics: number of functions/predicates satisfying a sum on their entries

Given integers $n,m$, is there a closed form expression for the cardinality of the following set? $$\left\{ p : \{1,\dots,n\}^2 \rightarrow \{true,false\} \quad \Bigg| \sum_{i,j,k \in \{1,\dots,n\}} ...
0
votes
2answers
37 views

Counting problem: ways of opening stores in non-adjacent blocks?

A coffee company wants to set up stores along the main street of town, which has $n$ blocks. The company won’t open two stores in the same block, or in two adjacent blocks. Q: For this coffee shop, ...
2
votes
0answers
56 views

Combinatorial formula for the number of different words

Does there exist a closed formula for the following: Suppose we have $m$ distinct letters and we are allowed to use each letter at most $d$ times. What is the number of distinct words of length $k?$ ...
1
vote
1answer
33 views

How can I find how many unique strings there are with an equal numbers of elements, given a string length and number of elements to choose from?

The question is all in the title. Here's an example: Elements: A, B; Length: 4: AABB ABAB ABBA BABA BBAA BAAB There are 6 such unique strings for 2 elements and ...
0
votes
0answers
21 views

Maximizing the following function

I need to find values of $k_1$, $k_2$ and $k_3$ that maximize $C^{m_1}_{mm_1} \cdot C^{m_2}_{k_1-mm_1} \cdot C^{n_1}_{nn_1} \cdot C^{n_2}_{k_2-nn_1} \cdot C^{p_1}_{pp_1} \cdot C^{p_2}_{k_3-pp_1}$ ...
2
votes
1answer
22 views

The generating set of Cayley graphs over $Z_n$

Say we have a undirected and connected Cayley graph over $\mathbb{Z}_n$, with generating set $S=\{\pm x_0,\pm x_1,\ldots,\pm x_k\}$. Is it true that we can assume without the loss of generality that ...
6
votes
2answers
136 views

Proof of an identity of $n!$

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is: \begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n ...
1
vote
0answers
12 views

Number of ways to connect sets of k vertices in a perfect n-gon [duplicate]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
4answers
46 views

How many three digit numbers with increasing digits can be formed from the set $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

Suppose we pick 3 numbers $x,y,z \in \{1,2,3,4,5,6,7,8\}$ and form a 3 digit number $xyz$ how many possible combinations numbers can we create such that $x < y < z$. For example $357$ ...
0
votes
3answers
43 views

Probability of choosing two numbers so they differ by at least 2

A box has $10$ balls numbered $1,2, \dots, 10.$ A ball is picked at random and then a second ball is picked at random from the remaining nine balls. Find the probability that the numbers on the two ...
2
votes
4answers
75 views

Two dice thrown together.

Each face of a die is marked with a different number from 1 to 6. The number on the faces of the die are marked in such a way that the sum of the numbers on any pair of opposite faces is 7. Two such ...
0
votes
0answers
18 views

Number of subset problem [duplicate]

Question: A woman is preparing to go for a party .She need to colour her nails (all her nails considered 10 nails) She want to use either pink nail polish or red nail polish to colour each nails. ...
3
votes
2answers
61 views

Set and subsets link by prime numbers

I have a bit idea to solve this problem for small $n$ by programation but I think for $n>100$ I will need maths to help me. My problem is : Let S be the set of prime numbers less than n. Find ...
5
votes
1answer
60 views

How to prove the maximum possible number of elements of $S$ is $48$?

Let set $S\subseteq \{1,2,3,\cdots,100\}$,for any two different $a,b\in S$,there exist postive integer $k$ and $c,d\in S(c<d)$,($c,d$ can equal to $a$ or $b$),such $$a+b=c^k\cdot d$$ show that ...
-6
votes
2answers
54 views

Chances of this… [on hold]

9 people sat in a circle. They wrote their name on a piece of paper, folded it over and placed it in a hat. The hat was shuffled to mix up the pieces of paper. The first person picked out the name ...
1
vote
1answer
16 views

Number of solutions to equation $\sum_{i=1}^{n}x_i = R$ where $x_i>k$ where $k$ is a positive number

I know that the number of solutions to an equation of the form: $$\sum_{i=1}^{n}x_i = R$$ equals $\binom{n+R-1}{R}$. I am aware of the $x_i$ LESS THAN EQUAL TO case where, if say $x_6 \leq 3$, I ...
0
votes
2answers
48 views

In how many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty?

How many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty? So if I do this similar to stars and bars I am looking to put $n$ balls in actually $n-1$ urns, so ...
0
votes
1answer
35 views

Dividing $n$ identical things into $r$ groups

I was reading a course on Combinatorics where I came across following: The number of ways in which $n$ identical things can be divided into $r$ groups so that no group contains less than $m$ items ...
2
votes
3answers
38 views

Number of words which can be formed with INSTITUTION such that vowels and consonants are alternate

Question: How many words which can be formed with INSTITUTION such that vowels and consonants are alternate? My Attempt: There are total 11 letters in word INSTITUTION. The 6 consonants are ...